/*
 * File:   infint.cpp
 * Author: ScaV
 *
 * Created on 17 РЎРµРЅС‚СЏР±СЂСЊ 2011 Рі., 23:01
 */

#include "infint.h"
#include <cmath>
#include <limits>
#include <conio.h>

infint::infint() {
	setDigit(0);
}

infint::infint(long long num) {
	setDigit(num);
}

infint::infint(std::string str) {
	setDigit(str);
}

infint::infint(const infint& orig) {
	this->copyFrom(orig);
}

infint::~infint() {
	delete digit;
}

int infint::getClustSize() {
	static int i = -1;
	if (i != -1)
		return i;
	infclust templ;
	templ = std::numeric_limits<infclust>::max();
	i = static_cast<int> (log10(templ));
	if (pow(10, i) / 10 * 2 > templ / 10)
		i--;
	return i;
}

infclust infint::getClustTemplate() {
	static infclust templ = 0;
	double pw;
	if (templ)
		return templ;
	pw = pow(10, getClustSize());
	templ = static_cast<infclust> (pw);
	return templ;
}

infclust infint::getClustMax() {
	return std::numeric_limits<infclust>::max();
}

int infint::setDigit(long long num) {
	int s = 1;
	if (num < 0) {
		num = -num;
		s = -1;
	}
	if (!setSign(s))
		return -1;
	if (!setModule(num))
		return -2;
	return 1;
}

int infint::setDigit(std::string str) {
	int s = 1, b = 0;
	if (str[0] == '+' || str[0] == '-')
		b = 1;
	if (str[0] == '-')
		s = -1;
	if (!setSign(s))
		return -1;
	if (!setModule(str.c_str() + b))
		return -2;
	return 1;
}

int infint::setModule(long long num) {
	infclust tmpl, div;
	digit = new arlist;
	tmpl = getClustTemplate();
	if (num < 0)
		return 0;
	while (num >= 1) {
		div = num % tmpl;
		digit->push_front(div);
		num /= tmpl;
	}
	return 1;
}

int infint::setModule(std::string str) {
	infclust num = 0, dis = 1;
	int i = 0, insig = 0, clsz = getClustSize();
	strriter b = str.rbegin(), e = str.rend();
	digit = new arlist;
	while (b != e) {
		num += static_cast<infclust> (*b - '0') * dis;
		i++;
		b++;
		dis *= 10;
		if (i >= clsz || b == e) {
			if (!num) {
				insig++;
			} else {
				while (insig > 0) {
					insig--;
					digit->push_front(0);
				}
				digit->push_front(num);
			}
			i = 0;
			num = 0;
			dis = 1;
		}
	}
	return 1;
}

int infint::setSign(char m) {
	if (m == '-' || m == -1) {
		sign = -1;
		return -1;
	} else if (m == '+' || m == 1) {
		sign = 1;
		return 1;
	}
	return 0;
}

infint infint::getSum(int sgn, const infint& l) {
	infint res;
	int zeromem = 0;
	arriter i1, i2, e1, e2;
	infclust w, tmpl, tsum, a1, a2;
	int m = 0;
	tmpl = getClustTemplate();
	i1 = digit->rbegin();
	e1 = digit->rend();
	i2 = l.digit->rbegin();
	e2 = l.digit->rend();
	while (1) {
		if (i1 == e1) a1 = 0;
		else a1 = *i1;
		if (i2 == e2) a2 = 0;
		else a2 = *i2;
		if (i1 == e1 && i2 == e2 && !m) break;
		tsum = a1 + a2 * sgn + m * sgn;
		if (tsum < 0) {
			tsum = tmpl + tsum;
			m = 1;
		} else m = tsum / tmpl;
		w = tsum % tmpl;
		if (w) {
			for (int z = 0; z < zeromem; ++z)
				res.digit->push_front(0);
			zeromem = 0;
			res.digit->push_front(w);
		} else
			++zeromem;
		if (i1 != e1) ++i1;
		if (i2 != e2) ++i2;
	}
	return res;
}

infint infint::getProduct(const infint& l) {
	infint res, temp;
	if (digit->empty() || l.digit->empty())
		return res;
	ariter i1, e1;
	arriter i2, e2;
	infpr tpr;
	infclust tmpl, m, w;
	int count = 0;
	tmpl = getClustTemplate();
	e1 = digit->end();
	e2 = l.digit->rend();
	for (i1 = digit->begin(); i1 != e1; ++i1) {
		if (count) res.digit->push_back(0);
		m = 0;
		temp.digit->clear();
		for (i2 = l.digit->rbegin(); i2 != e2; ++i2) {
			tpr = static_cast<infpr> (*i1) * static_cast<infpr> (*i2) + m;
			w = tpr % tmpl;
			m = tpr / tmpl;
			temp.digit->push_front(w);
		}
		if (m)
                    temp.digit->push_front(m);
		res = res.getSum(1, temp);
		++count;
	}
	res.sign = sign * l.sign;
	return res;
}

infint infint::getDivide(infint& l, infint* tail) {

	if (l.digit->empty())
		throw "Panic! %) Devided by zero!";
	infint res, temp, ten(10);
	short dd, dr;
        float add;
	bool isbreak = false, count;
	long drlen = l.getLength(), tlen;
	long iter = drlen;
	if (tail)
		tail->copyFrom(l);
	if (temp.cutFrom(*this, 0, iter) < iter)
		return res;
	while (1) {
		tlen = temp.getLength();
		count = false;
		while (tlen < drlen || temp.getEqualDigits(l) < 0) {
			if (count)
				res = res.getProduct(ten);
			if ((*this)[iter] == -7) {
				isbreak = true;
				break;
			}
			temp = (temp.getProduct(ten)).getSum(1, (*this)[iter]);//Add one more
			++iter;
			++tlen;
			count = true;
		}
		if (isbreak) break;
		dd = temp[0];
		dr = l[0];
                if (l.getLength() < temp.getLength())
                    dd = dd * 10 + temp[1];
                add = dd / dr;
                if (add > 10) add = 10;
                while (temp.getEqualDigits(l.getProduct(add)) < 0) {
                    --add;
                }
		res = res * 10 + add;
		temp = temp.getSum(-1, l.getProduct(add)); //temp = temp - (l * add);
	}
	res.sign = sign * l.sign;
	if (tail)
		tail->copyFrom(temp);
	return res;
}

infint infint::getPow(infint l2) {
	static infint tmp, one(1), two(2), null, tail;
	if (l2 < 1)
		return one;
	if (l2 == 1)
		return *this;
	tmp = this->getPow(l2.getDivide(two, &tail));
	if (tail != null)
		tmp = tmp.getProduct(tmp.getProduct(*this));
	else
		tmp = tmp.getProduct(tmp);
	return tmp;
}

int infint::getEqualSigns(const infint& l2) {
	if (sign > l2.sign)
		return 1;
	if (sign < l2.sign)
		return -1;
	return 0;
}

int infint::getEqualDigits(const infint& l2) {
	arriter i1, e1, i2, e2;
	int state = 0;
	i1 = digit->rbegin();
	e1 = digit->rend();
	i2 = l2.digit->rbegin();
	e2 = l2.digit->rend();
	while (1) {
		if (i1 == e1 && i2 == e2) return state;
		if (i1 == e1) return -1;
		if (i2 == e2) return 1;
		if (*i1 > *i2) state = 1;
		else if (*i1 < *i2) state = -1;
		++i1;
		++i2;
	}
}

long infint::getLength() {
	long length;
	length = this->digit->size();
	if (!length)
		return 0;
	length = (length - 1) * getClustSize();
	length += static_cast<long> (log10(this->digit->front())) + 1;
	return length;
}

void infint::copyFrom(const infint& orig) {
	sign = orig.sign;
	digit = new arlist;
	*digit = *(orig.digit);
	return;
}

long infint::cutFrom(infint& orig, long start, long numof) {

	if (orig.digit->empty() || start < 0 || numof <= 0)
		return 0;

	ariter iter = orig.digit->begin(),
			iend = orig.digit->end();
	long i, k, t,
			count = -1,
			clsz = getClustSize();
	infclust tmpl;

	for (i = 0; ; ++i) {
		if (!(i % clsz)) {
			tmpl = getClustTemplate() / 10;
			if (i)	++iter;
		}
		if (iter == iend)
			return 0;
		if (count < 0 && (*iter / tmpl)) {
			count = 0;		//Нашли разряд старта
			t = i;
		}
		if (count >= start)
			break;
		if (count > -1)
			++count;
		tmpl /= 10;
	}

	infclust add = 0;
	bool wasfirst = false;
	int corr = (clsz - (numof % clsz)) % clsz;	//Коррекция старта цикла

	digit->clear();
	for (k = corr; k <= numof + corr; ++k, ++i) {
		if (!(i % clsz)) {
			tmpl = getClustTemplate() / 10;
			if (i) ++iter;
		}
		if (!(k % clsz) || (iter == iend || k >= numof + corr)) {
			if (add || wasfirst) {
				digit->push_back(add);
				wasfirst = true;
				add = 0;
			}
			if (iter == iend || k >= numof + corr)
				break;
		}
		add *= 10;
		add += (*iter / tmpl) % 10;
		tmpl /= 10;
	}

	return i - t;
}

infint& infint::operator =(infint src) {
	if (this == &src)
		return *this;
	delete digit;
	this->copyFrom(src);
	return *this;
}

infint& infint::operator ++() {
	*this = *this+1;
	return *this;
}

infint infint::operator ++(int) {
	infint tmp = *this;
	*this = *this+1;
	return tmp;
}

infint& infint::operator --() {
	*this = *this-1;
	return *this;
}

infint infint::operator --(int) {
	infint tmp = *this;
	*this = *this-1;
	return tmp;
}

infint infint::operator -() {
	infint res(*this);
	res.sign *= -1;
	return res;
}

infint infint::getFact() {
	if (*this < 1)
		return *this;
	infint c, res(1);
	for (c = 1; c <= *this; ++c)
		res = res.getProduct(c);
	return res;
}

infint infint::getFib() {
	infint i, c1(1), c2, fib(1);
	for(i = 1;i < *this; ++ i) {
		c1 = c2;
		c2 = fib;
		fib = c1 + c2;
	}
	return fib;
}

short infint::operator [](int index) {
	infclust tmpl;
	ariter iter = digit->begin(),
			iend = digit->end();
	long i,
			count = -1,
			clsz = getClustSize();
	if (index == -1)
		return sign;
	for (i = 0; ; ++i) {
		if (!(i % clsz)) {
			tmpl = getClustTemplate() / 10;
			if (i)	++iter;
		}
		if (iter == iend)
			return -7;
		if (count < 0 && (*iter / tmpl))
			count = 0;		//Нашли разряд старта
		if (count >= index)
			return (*iter / tmpl) % 10;
		if (count > -1)	++count;
		tmpl /= 10;
	}
}

void infint::operator +=(infint n) {
	*this = *this + n;
}

void infint::operator -=(infint n) {
	*this = *this - n;
}

void infint::operator *=(infint n) {
	*this = *this * n;
}

void infint::operator /=(infint n) {
	*this = *this / n;
}

void infint::operator ^=(infint n) {
	*this = this->getPow(n);
}

infint operator +(infint l1, infint l2) {
	infint *send1 = &l1, *send2 = &l2, res;
	int sendsign = 1, ressign = 1;
	if (l1.getEqualDigits(l2) < 0) {
		send1 = &l2;
		send2 = &l1;
	}
	sendsign *= send1->sign * send2->sign;
	ressign *= sendsign * send2->sign;
	res = send1->getSum(sendsign, *send2);
	res.sign = ressign;
	return res;
}

infint operator -(infint l1, infint l2) {
	infint *send1 = &l1, *send2 = &l2, res;
	int sendsign = 1, ressign = 1;
	if (l1.getEqualDigits(l2) < 0) {
		send1 = &l2;
		send2 = &l1;
		ressign *= -1;
	}
	sendsign *= send1->sign * send2->sign * -1;
	ressign *= sendsign * send2->sign * -1;
	res = send1->getSum(sendsign, *send2);
	res.sign = ressign;
	return res;
}

infint operator *(infint l1, infint l2) {
	return l1.getProduct(l2);
}

infint operator /(infint l1, infint l2) {
	return l1.getDivide(l2);
}

infint operator %(infint l1, infint l2) {
	infint res;
	l1.getDivide(l2, &res);
	return res;
}

infint operator ^(infint l1, infint l2) {
	return l1.getPow(l2);
}

bool operator ==(infint l1, infint l2) {
	if (l1.digit->empty() && l2.digit->empty())
		return 1;
	if (l1.getEqualSigns(l2) != 0)
		return 0;
	if (l1.getEqualDigits(l2) != 0)
		return 0;
	return 1;
}

bool operator !=(infint l1, infint l2) {
	if (l1.digit->empty() && l2.digit->empty())
		return 0;
	if (l1.getEqualSigns(l2) == 0 && l1.getEqualDigits(l2) == 0)
		return 0;
	return 1;
}

bool operator>(infint l1, infint l2) {
	int es = l1.getEqualSigns(l2), ed = l1.getEqualDigits(l2), s = l1.sign;
	if (es == 1)
		return 1;
	else if (es == 0 && (s == 1 && ed > 0 || s == -1 && ed < 0))
		return 1;
	return 0;
}

bool operator<(infint l1, infint l2) {
	int es = l1.getEqualSigns(l2), ed = l1.getEqualDigits(l2), s = l1.sign;
	if (es == -1)
		return 1;
	else if (es == 0 && (s == 1 && ed < 0 || s == -1 && ed > 0))
		return 1;
	return 0;
}

bool operator >=(infint l1, infint l2) {
	int es = l1.getEqualSigns(l2), ed = l1.getEqualDigits(l2), s = l1.sign;
	if (es == 1)
		return 1;
	else if (es == 0 && (s == 1 && ed >= 0 || s == -1 && ed <= 0))
		return 1;
	return 0;
}

bool operator <=(infint l1, infint l2) {
	int es = l1.getEqualSigns(l2), ed = l1.getEqualDigits(l2), s = l1.sign;
	if (es == -1)
		return 1;
	else if (es == 0 && (s == 1 && ed <= 0 || s == -1 && ed >= 0))
		return 1;
	return 0;
}

std::ostream& operator <<(std::ostream& s, infint t) {
	ariter iter, end, begin;
	if (t.digit->empty()) {
		s << "0";
	} else {
		if (t.sign < 0)
			s << "-";
		end = t.digit->end();
		begin = t.digit->begin();
		for (iter = begin; iter != end; ++iter) {
			int count = t.getClustSize() - static_cast<int>((*iter > 0)?(log10(*iter)):(0));
			for (int h = 1; h < count && iter != begin; ++h)
				s << 0;					//Забиваем нулями
			s << *iter << " ";
		}
	}
	return s;
}

